package Top_Interview_Questions.Hash_Table;

import java.util.Arrays;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/9 16:49
 * <p>
 * 功能描述:
 */
public class _0204 {

    /**
     * https://leetcode-cn.com/problems/count-primes/solution/ru-he-gao-xiao-pan-ding-shai-xuan-su-shu-by-labula/
     */
    int countPrimes(int n) {
        boolean[] isPrim = new boolean[n];
        Arrays.fill(isPrim, true);
        for (int i = 2; i * i < n; i++)
            if (isPrim[i])
                for (int j = i * i; j < n; j += i)
                    isPrim[j] = false;

        int count = 0;
        for (int i = 2; i < n; i++)
            if (isPrim[i]) count++;

        return count;
    }


}
